package com.company;

import com.sun.xml.internal.stream.XMLInputFactoryImpl;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static int minimumTotal1(List<List<Integer>> triangle){
        int result = 0;
        int k = 0;
        int l = triangle.size();
        if(l == 0)return 0;
        result += triangle.get(0).get(0);
        for(int i=1;i<l;i++){
            if (triangle.get(i).get(k) < triangle.get(i).get(k+1)){
                result += triangle.get(i).get(k);
            }else{
                result += triangle.get(i).get(k+1);
                k = k+1;
            }
        }
        return result;
    }
    public static int row = 0;
    public static List<List<Integer>> aa;
    public static int help(int level,int i,int j){
        if (level == row){
            return 0;
        }
        int a = Integer.MAX_VALUE;
        int b =0;
        if(i>=0&&i<row){
            a = help(level+1,i,i+1) + aa.get(level).get(i);
        }
        if(j>=0&&j<row){
            b = help(level+1,j,j+1) + aa.get(level).get(j);
        }
        return Math.min(a,b);
    }
    public static int minimumTotal(List<List<Integer>> triangle){
        aa = triangle;
        row = aa.size();
        System.out.println(aa+","+row);

        return help(0,-1,0);
    }

    public static int minimumTotal2(List<List<Integer>> triangle){
        int row = triangle.size();
        int []dp = new int[row];
        for(int i=0;i<row;i++)dp[i] = triangle.get(row-1).get(i);
        System.out.println(Arrays.toString(dp));
        for(int i=row-2;i>=0;i--){
            for(int j=0;j<i+1;j++){
                dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[0];
    }
    public static void main(String[] args) {
	// write your code here
        List<List<Integer>>a = new ArrayList<List<Integer>>();
        a.add(new ArrayList<Integer>(){{add(2);}});
        a.add(new ArrayList<Integer>(){{add(3);add(4);}});
        a.add(new ArrayList<Integer>(){{add(6);add(5);add(7);}});
        a.add(new ArrayList<Integer>(){{add(4);add(1);add(8);add(3);}});
        System.out.println(a);
        System.out.println(minimumTotal2(a));
    }
}
